public class Answer2 {
    // 链表相加
    //https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=196&tqId=37147&ru=/exam/oj

    public static class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }

    public static void main(String[] args) {
        ListNode head1=new ListNode(9);
        head1.next=new ListNode(3);
        head1.next.next=new ListNode(7);
        ListNode head2=new ListNode(6);
        head2.next=new ListNode(3);
        System.out.println(addInList(head1, head2));
    }
    public static ListNode addInList (ListNode head1, ListNode head2) {
        ListNode cur1 = head1;
        int num1 = 0;
        while (cur1 != null) {
            num1++;
            cur1 = cur1.next;
        }
        ListNode cur2 = head2;
        int num2 = 0;
        while (cur2 != null) {
            num2++;
            cur2 = cur2.next;
        }
        int n = num1 - num2;
        if (n > 0) {
            while (n-- != 0) {
                ListNode cur = new ListNode(0);
                cur.next = head2;
                head2 = cur;
            }
        } else if (n < 0) {
            while (n-- != 0) {
                ListNode cur = new ListNode(0);
                cur.next = head1;
                head1 = cur;
            }
        }

        ListNode cur=addList(head1,head2);
        return cur.val==0 ? cur.next :cur;
    }

    public static ListNode addList (ListNode head1, ListNode head2){
        if(head1.next == null ){
            int a=head1.val+head2.val;
            ListNode curhead=new ListNode(a/10);
            curhead.next=new ListNode(a%10);
            return curhead;
        }else{
            ListNode cur=addList(head1.next,head2.next);
            int b=cur.val+head1.val+head2.val;
            ListNode curhead=new ListNode(b/10);
            curhead.next=new ListNode(b%10);
            curhead.next.next=cur.next;
            return curhead;
        }
    }
    /*public static ListNode reverse(ListNode list){
        ListNode curHead=new ListNode(0);
        ListNode cur=list;
        while(cur!=null){
            // 逆置
            ListNode curnext=cur.next;
            cur.next=curHead.next;
            curHead.next=cur;
            cur=curnext;
        }
        return curHead.next;
    }
    public static ListNode addInList (ListNode head1, ListNode head2) {
        // 逆置
        head1=reverse(head1);
        head2=reverse(head2);
        //实现加法
        int t=0;
        ListNode cur1=head1,cur2=head2;
        ListNode cur=new ListNode(0);
        ListNode prev=cur;
        while(cur1!=null || cur2!=null || t!=0){
            if(cur1!=null){
                t+=cur1.val;
                cur1=cur1.next;
            }
            if(cur2!=null){
                t+=cur2.val;
                cur2=cur2.next;
            }
            prev.next=new ListNode(t%10);
            prev=prev.next;
            t/=10;
        }

        return reverse(cur.next);
    }*/
}
